package org.example.myleet.p992;

public class Solution1 {
    /**
     * 4 ms
     * 官方正解如下，将问题从恰好转化成最多，这样每次移动右指针时，可以利用动态规划思想直接得出新增子数组的个数
     */
    public int subarraysWithKDistinct(int[] A, int K) {
        //问题转化成最多K - 最多k-1，得到恰好有K个数的结果
        return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
    }

    /**
     * @param A
     * @param K
     * @return 最多包含 K 个不同整数的子区间的个数
     */
    private int atMostKDistinct(int[] A, int K) {
        int len = A.length;
        int[] freq = new int[len + 1];

        int left = 0;
        int right = 0;
        // [left, right) 里不同整数的个数
        int count = 0;
        int res = 0;
        // [left, right) 包含不同整数的个数小于等于 K
        while (right < len) {
            if (freq[A[right]] == 0) {
                count++;
            }
            freq[A[right]]++;
            right++;

            while (count > K) {
                freq[A[left]]--;
                if (freq[A[left]] == 0) {
                    count--;
                }
                left++;
            }
            // [left, right) 区间的长度就是对结果的贡献
            //可以借鉴动态规划的思想，举个例子就好理解了：
            //当满足条件的子数组从[A,B,C]增加到[A,B,C,D]时，新子数组的长度为4，同时增加的子数组为[D],[C,D],[B,C,D],[A,B,C,D]也为4。
            res += right - left;
        }
        return res;
    }
}
